package com.tgy.leetcode;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 1/18/21 10:17 AM
 *
 *
 *  https://leetcode-cn.com/problems/accounts-merge/
 */
public class _721_账户合并 {


    public List<List<String>> accountsMerge(List<List<String>> accounts) {


        if (accounts.size() == 0) {

            return new ArrayList<>();
        }

        int[] parents = new int[accounts.size()];

        for (int i = 0; i < parents.length; i++) {

            parents[i] = i;
        }

        Map<String,Integer> map = new HashMap<>();

        for (int i = 0; i < accounts.size(); i++) {
            //
            List<String> account = accounts.get(i);

            for (int i1 = 1; i1 < account.size(); i1++) {

                String email = account.get(i1);
                if (map.get(email) == null) {

                    map.put(email,i);
                }else {

                    union(parents,map.get(email),i);
                }
            }
        }


        Map<Integer,HashSet<String>> result = new HashMap<>();

        for (int i = 0; i < accounts.size(); i++) {
            //
            List<String> account = accounts.get(i);

            for (int i1 = 1; i1 < account.size(); i1++) {

                String email = account.get(i1);

                int p1 = find(parents,map.get(email));

                HashSet<String> emails = result.get(p1);
                if (emails == null) {

                    emails = new HashSet<>();
                    result.put(p1,emails);
                }
                emails.add(email);
            }
        }

        List<List<String>> res = new ArrayList<>();
        for (Map.Entry<Integer, HashSet<String>> integerHashSetEntry : result.entrySet()) {
          //

            ArrayList<String> account = new ArrayList<>(integerHashSetEntry.getValue());
            Collections.sort(account);
            String name = accounts.get(integerHashSetEntry.getKey()).get(0);
            account.add(0,name);
            res.add(account);
        }

        return res;
    }

    private int find(int[] parents, int k) {

        if (parents[k] != k) {

            parents[k] = find(parents,parents[k]);
        }

        return parents[k];
    }

    private void union(int[] parents,int k1, int k2) {

        int p1 = find(parents, k1);
        int p2 = find(parents, k2);

        if (p1 == p2) {

            return;
        }

        parents[p2] = p1;
    }

      public static void main(String[] args) {
        //
        _721_账户合并 accountsMerge = new _721_账户合并();

        List<List<String>> params = new ArrayList<>();

        params.add(new ArrayList<>(Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com")));
        params.add(new ArrayList<>(Arrays.asList("John", "johnnybravo@mail.com")));
        params.add(new ArrayList<>(Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com")));
        params.add(new ArrayList<>(Arrays.asList("Mary", "mary@mail.com")));

        accountsMerge.accountsMerge(params);

      }
}
